package org.hot100.h148;


/**
 * @Author: wjy
 * @Date: 2021/12/31 13:18
 */
public class Solution {

    /**
     * 给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
     *
     * 示例 1：
     *
     * 输入：head = [4,2,1,3]
     * 输出：[1,2,3,4]
     *
     * 示例 2：
     *
     * 输入：head = [-1,5,3,4,0]
     * 输出：[-1,0,3,4,5]
     *
     * 示例 3：
     *
     * 输入：head = []
     * 输出：[]
     *
     * @param args
     */
    public static void main(String[] args) {

        ListNode listNode1 = new ListNode(4);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(1);
        ListNode listNode4 = new ListNode(3);

        listNode3.next = listNode4;
        listNode2.next = listNode3;
        listNode1.next = listNode2;

        Solution solution = new Solution();
        ListNode res = solution.sortList5(listNode1);
        while (res != null) {
            System.out.println(res.val);
            res = res.next;
        }
    }

    /*public ListNode sortList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode mid = slow.next;
        slow.next = null;

        ListNode left = this.sortList2(head);
        ListNode right = this.sortList2(mid);

        ListNode node = new ListNode(-1);
        ListNode temp = node;

        // 链表排序
        while (left != null && right != null) {
            if (left.val > right.val) {
                node.next = right;
                right = right.next;
            } else {
                node.next = left;
                left = left.next;
            }
            node = node.next;
        }

        node.next = left == null ? right : left;

        return temp.next;
    }*/

    public ListNode sortList2(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 利用快慢指针，找出中间节点，用作归并排序
        ListNode slow = head, fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 中间节点
        ListNode mid = slow.next;

        // 此处 slow.next 必须为空，否则不能达到分段排序的目的
        slow.next = null;

        ListNode left = sortList2(head);
        ListNode right = sortList2(mid);

        // 辅助变量，用于合并 left、right 节点
        ListNode node = new ListNode();
        ListNode n = node;
        while (left != null && right != null) {
            if (left.val < right.val) {

                // 如果 left.val < right.val 成立，将 left 添加到 n 节点后
                n.next = left;
                left = left.next;
            } else {

                // 如果 left.val < right.val 成立，将 right 添加到 n 节点后
                n.next = right;
                right = right.next;
            }

            // 这他🐎还👀不明白？？？
            n = n.next;
        }

        // 将前面循环没遍历完的添加到 node 最后节点，如果 left 为空证明 left 已经遍历完，所以将 right 添加至最后，反之同理
        n.next = left == null ? right : left;

        return node.next;
    }

    public ListNode sortList3(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode slow = head;
        ListNode fast = head.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        ListNode mid = slow.next;
        slow.next = null;

        ListNode left = sortList3(head);
        ListNode right = sortList3(mid);

        ListNode n = new ListNode();
        ListNode temp = n;
        while (left != null && right != null) {
            if (left.val < right.val) {
                n.next = left;
                left = left.next;
            } else {
                n.next = right;
                right = right.next;
            }
            n = n.next;
        }

        n.next = left == null ? right : left;
        return temp.next;
    }

    public ListNode sortList4(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode slow = head, fast = head.next, mid;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        mid = slow.next;
        slow.next = null;
        ListNode left = sortList4(head);
        ListNode right = sortList4(mid);
        ListNode node = new ListNode();
        ListNode temp = node;
        while (left != null && right != null) {
            if (left.val < right.val) {
                node.next = left;
                left = left.next;
            } else {
                node.next = right;
                right = right.next;
            }
            node = node.next;
        }

        node.next = left == null ? right : left;
        return temp.next;
    }

    public ListNode sortList5(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        ListNode slow = head, fast = head.next, mid = null, temp = null;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        mid = slow.next;
        slow.next = null;

        ListNode left = sortList5(head);
        ListNode right = sortList5(mid);
        ListNode node = new ListNode();
        temp = node;
        while (left != null && right != null) {
            if (left.val < right.val) {
                node.next = left;
                left = left.next;
            } else {
                node.next = right;
                right = right.next;
            }
            node = node.next;
        }

        node.next = left == null ? right : left;
        return temp.next;
    }

    public ListNode sortList(ListNode head) {
        // 1、递归结束条件
        if (head == null || head.next == null) {
            return head;
        }

        // 2、找到链表中间节点并断开链表 & 递归下探
        ListNode midNode = middleNode(head);
        ListNode rightHead = midNode.next;
        midNode.next = null;

        ListNode left = sortList(head);
        ListNode right = sortList(rightHead);

        // 3、当前层业务操作（合并有序链表）
        return mergeTwoLists(left, right);
    }

    //  找到链表中间节点（876. 链表的中间结点）
    private ListNode middleNode(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode slow = head;
        ListNode fast = head.next.next;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }

    // 合并两个有序链表（21. 合并两个有序链表）
    private ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode sentry = new ListNode(-1);

        // 中间商
        ListNode curr = sentry;

        while(l1 != null && l2 != null) {
            if(l1.val < l2.val) {
                curr.next = l1;
                l1 = l1.next;
            } else {
                curr.next = l2;
                l2 = l2.next;
            }

            curr = curr.next;
        }

        curr.next = l1 != null ? l1 : l2;
        return sentry.next;
    }

}

class ListNode {
    int val;
    ListNode next;
    ListNode() {};
    ListNode(int x) {
        val = x;
        next = null;
    }
}